The invention relates to a method and apparatus for data communication in a network.
Conventionally, integrating different network protocols or media types is complex and difficult. Routers and gateways may be used for protocol conversion and for managing quality of services. However, these techniques and devices tend to be complex, resource intensive, difficult and time consuming to implement and slow in operation.
In conventional high speed networks, data is typically transmitted in a single format, e.g., ATM, frame relay, PPP, Ethernet, etc. Each of these various types of formats generally requires dedicated hardware and communication paths along which to transmit the data. The principle reason for this is that the communication protocols and signaling techniques tend to be different for each format. For example, in a transmission using an ATM format, data cells are sent from a source to a destination along a predetermined path. Headers are included with each cell for identifying the cell as belonging to a set of associated data. In such a transmission, the size of the data cell being sent is known, as well as the beginning and end of the cell. In operation, cells are sent out, sometimes asynchronously, for eventual reassembly with the other associated data cells of the set at a destination. Idle times may occur between transmissions of data cells.
For a frame relay format, communications are arranged as data frames. Data is sent sometimes asynchronously for eventual reassembly with other associated data packets at a destination. Idle time may occur between the transmissions of individual frames of data. The transmission and assembly of frame relay data, however, is very different from that of ATM transmissions. For example, the frame structures differ as well as the manner in which data is routed to its destination.
Some network systems require that connections be set up for each communication session and then be taken down once the session is over. This makes such systems generally incompatible with those in which the data is routed as discrete packets. A Time Division Multiplex (TDM) system, for example, requires the setting up of a communication session to transmit data. While a communication session is active, there is no time that the communication media can be considered idle, unlike the idle periods that occur between packets in a packet-based network. Thus, sharing transmission media is generally not possible in conventional systems. An example of this type of protocol is xe2x80x9cPoint-to-Point Protocolxe2x80x9d (PPP). Internet Protocol (IP) is used in conjunction with PPP in manner known as IP over PPP to forward IP packets between workstations in client-server networks.
It would be useful to provide a network system that allows data of various different formats to be transmitted from sources to destinations within the same network and to share transmission media among these different formats.
As mentioned, some network systems provide for communication sessions. This scheme works well for long or continuous streams of data, such as streaming video data or voice signal data generated during real-time telephone conversations. However, other network systems send discrete data packets that may be temporarily stored and forwarded during transmission. This scheme works well for communications that are tolerant to transmission latency, such as copying computer data files from one computer system to another. Due to these differences in network systems and types of data each is best suited for, no one network system is generally efficient and capable of efficiently handling mixed streams of data and discrete data packets.
Therefore, what is needed is a network system that efficiently handles both streams of data and discrete data packets.
Further, within conventional network systems, data packets are received at an input port of a multi-port switch and are then directed to an appropriate output port based upon the location of the intended recipient for the packet. Within the switch, connections between the input and output ports are typically made by a crossbar switch array. The crossbar array allows packets to be directed from any input port to any output port by making a temporary, switched connection between the ports. However, while such a connection is made and the packet is traversing the crossbar array, the switch is occupied. Accordingly, other packets arriving at the switch are blocked from traversing the crossbar. Rather, such incoming packets must be queued at the input ports until the crossbar array becomes available.
Accordingly, the crossbar array limits the amount of traffic that a typical multi-port switch can handle. During periods of heavy network traffic, the crossbar array becomes a bottleneck, causing the switch to become congested and packets lost by overrunning the input buffers.
An alternate technique, referred to as cell switching, is similar except that packets are broken into smaller portions called cells. The cells traverse the crossbar array individually and then the original packets are reconstructed from the cells. The cells, however, must be queued at the input ports while each waits its turn to traverse the switch. Accordingly, cell switching also suffers from the drawback that the crossbar array can become a bottleneck during periods of heavy traffic.
Another technique, which is a form of time-division multiplexing, involves allocating time slots to the input ports in a repeating sequence. Each port makes use of the crossbar array during its assigned time slots to transmit entire data packets or portions of data packets. Accordingly, this approach also has the drawback that the crossbar array can become a bottleneck during periods of heavy traffic. In addition, if a port does not have any data packets queued for transmission when its assigned time slot arrives, the time slot is wasted as no data may be transmitted during that time slot.
Therefore, what is needed is a technique for transmitting data packets in a multi-port switch that does not suffer from the afore-mentioned drawbacks. More particularly, what is needed is such a technique that avoids a crossbar array from becoming a traffic bottleneck during periods of heavy network traffic.
Under certain circumstances, it is desirable to send the same data to multiple destinations in a network. Data packets sent in this manner are conventionally referred to as multi-cast data. Thus, network systems must often handle both data intended for a single destination (conventionally referred to as uni-cast data) and multi-cast data. Data is conventionally multi-cast by a multi-port switch repeatedly sending the same data to all of the destinations for the data. Such a technique can be inefficient due to its repetitiveness and can slow down the network by occupying the switch for relatively long periods while multi-casting the data.
Therefore, what is needed is an improved technique for handling both uni-cast and multi-cast data traffic in a network system.
Certain network protocols require that switching equipment discover aspects of the network configuration in order to route data traffic appropriately (this discovery process is sometimes referred to as xe2x80x9clearningxe2x80x9d). For example, an Ethernet data packet includes a MAC source address and a MAC destination address. The source address uniquely identifies a particular piece of equipment in the network (i.e. a network xe2x80x9cnodexe2x80x9d) as the originator of the packet. The destination address uniquely identifies the intended recipient node (sometimes referred to as the xe2x80x9cdestination nodexe2x80x9d). Typically, the MAC address of a network node is programmed into the equipment at the time of its manufacture. For this purpose, each manufacturer of network equipment is assigned a predetermined range of addresses. The manufacturer then applies those addresses to its products such that no two pieces of network equipment share an identical MAC address.
A conventional Ethernet switch must learn the MAC addresses of the nodes in the network and the locations of the nodes relative to the switch so that the switch can appropriately direct packets to them. This is typically accomplished in the following manner: when the Ethernet switch receives a packet via one of its input ports, it creates an entry in a look-up table. This entry includes the MAC source address from the packet and an identification of the port of the switch by which the packet was received. Then, the switch looks up the MAC destination address included in the packet in this same look-up table. This technique is suitable for a local area network (LAN). However, where a wide area network (WAN) interconnects LANs, a distributed address table is required as well as learning algorithms to create and maintain the distributed table.
The invention is a technique for forwarding multi-cast data packets in a communication network. Multi-cast packets are broadcast to every output port of the switch. The packet is thus buffered in each port. Then, all of the output ports, save those that are appropriate output ports for the packet, drop the packet. Accordingly, the output ports that did not drop the packet forward the packet to the network. A control packet that follows the packet may then instruct the ports regarding which ports are to drop the packet and which ports are to forward the packet. This technique has an advantage of efficiently handling multi-cast packets.
In one aspect, a method of forwarding data packets in a multi-port switch having input ports for receiving data packets to be forwarded by the switch and output ports for forwarding the data packets is provided. A data packet is received by an input port. Copies of the data packet are passed to each of a plurality of output ports including at least one output port that is not an appropriate output port for forwarding the packet. One or more masks for the packet are formed, each mask being a binary value having a first logic value in each bit position that corresponds to appropriate output port for forwarding the packet and a second logic value in remaining bit positions. The data packet is forwarded by each appropriate output port indicated by the one or more masks.
The mask for a uni-cast packet may have the first logic value in a bit position that corresponds to one appropriate output port for forwarding the packet and a second logic value in the remaining bit positions. The mask for a multi-cast packet may have the first logic value in bit positions that correspond to a plurality of appropriate output ports for forwarding the packet and the second logic value in the remaining bit positions. The copy of the data packet may be dropped by each of the plurality of output ports that is not an appropriate output port for forwarding the data packet after said passing. The data packet may be forwarded by multiple output ports in substantially the same format. A plurality of the masks may be formed. The data packet may be forwarded in a different format for each of multiple output ports.
The mask may be included in a destination vector for the packet, wherein the destination vector indicates whether the packet is to be forwarded according to multiple different formats. The destination vector may be looked up in a look-up table of the multi-port switch. A command packet may be formed when the data packet is to be forwarded according to multiple different formats. The command packet may include indicia of the format for the data packet for each appropriate output port for forwarding the data packet. The command packet may include the one or more masks for the packet. The command packet may include an additional mask having the first logic value in all bit positions.
In another aspect, a method of forwarding data packets in a multi-port switch having input ports for receiving data packets to be forwarded by the switch and output ports for forwarding the data packets is provided. A data packet is received by an input port. Copies of the data packet are passed to each of a plurality of output ports including at least one output port that is not an appropriate output port for forwarding the packet. A determination is made as to whether the data packet is multi-cast or uni-cast. When the packet is uni-cast, a uni-cast mask is formed for the packet, the uni-cast mask being a binary value having first logic value in a bit position that corresponds to an appropriate output port for forwarding the packet and a second logic value in remaining bit positions. When the packet is multi-cast, a plurality of multi-cast masks are formed for the packet, each multi-cast mask being a binary value having the first logic value in a bit position that corresponds to an appropriate output port for forwarding the packet.
The data packet may be forwarding by the destination ports indicated by the one of the uni-cast or mult-cast masks. The copy of the data packet may be dropped by each of the plurality of output ports that is not an appropriate output port for forwarding the data packet after the copies are passed. When the data packet is multi-cast, an appropriate format of the data packet may be determined for each multi-cast mask. The data packet may be formatted in accordance with each of the appropriate formats thereby forming a plurality of formatted multi-cast packets. The formatted multi-cast packets may then be forwarded. A multi-cast identification list may be formed having a number of entries corresponding to the number of output ports that are to forward the data packet, each entry including an identification of a output port and an indication of an appropriate format for the data packet. The multi-cast masks may be formed based on the output port identifications.
In a further aspect, a method of forwarding data packets in a multi-port switch having input ports for receiving data packets to be forwarded by the switch and output ports for forwarding the data packets is provided. A data packet is received by an input port.
Copies of the data packet are passed to each of a plurality of output ports. One or more masks is formed for the packet, each mask being a binary value having a first logic value in one or more bit positions that correspond to appropriate output ports for forwarding the packet and a second logic value in the remaining bit positions. An appropriate format of the data packet is determined for each of the appropriate output ports. The data packet is formatted in accordance with each of the appropriate formats thereby forming a plurality of formatted multi-cast packets. The formatted multi-cast packets are forwarded. The copy of the data packet may be dropped by each output port that is not an appropriate output port for forwarding the data packet after said passing.
In still another aspect, a method of forwarding data packets in a multi-port switch having input ports for receiving data packets to be forwarded by the switch and output ports for forwarding the data packets is provided. A data packet is received by an input port. A first mask is formed when the packet is multi-cast, the first mask being a binary value having a first logic value in all bit positions. Copies of the data packet are passed to each output port indicated by the first mask, including at least one output port that is not an appropriate output port for forwarding the packet. One or more multi-cast masks are formed for the packet, each multi-cast mask being a binary value having a first logic value in each bit position that corresponds to appropriate output port for forwarding the packet and a second logic value in remaining bit positions. The data packet is forwarded by each appropriate output port indicated by the one or more multi-cast masks.
A determination may be made as to whether the packet is uni-cast or multi-cast. When the packet is uni-cast, a uni-cast mask may be formed, the uni-cast mask being a binary value having a first logic value each bit position that corresponds to appropriate output port for forwarding the packet. The uni-cast mask may have one occurrence of the first logic value or a plurality of occurrences of the first logic value. The uni-cast mask may be appended to the packet. The first mask may be appended to the data packet.